package _mst;

import _object.ListNode;

/**
 * 面试题 02.04. 分割链表
 */
public class T0204 {
    public ListNode partition(ListNode head, int x) {
        ListNode l1 = new ListNode(), l2 = new ListNode(), dummy1 = l1, dummy2 = l2;
        while (head != null) {
            if (head.val < x) {
                l1.next = new ListNode(head.val);
                l1 = l1.next;
            } else {
                l2.next = new ListNode(head.val);
                l2 = l2.next;
            }
            head = head.next;
        }
        l1.next = dummy2.next;
        return dummy1.next;
    }
}
